class Solution {
public:
    int calculate(string s) {
        stack<int> operands;  //存储表达式中的数值
        stack<int> operators; //存储表达式中的运算符
        int index = 0;
        /* 移除用户输入表达式中包含的无用的空格 */
        s.erase(remove(s.begin(), s.end(), ' '), s.end());
        while(index < s.size()){
            if(isdigit(s[index])){
                /* 将字符串转化为数字 */
                int digit = 0;
                for(;index < s.size() && isdigit(s[index]);index++)
                    digit = 10 * digit + (s[index] - '0');
                operands.push(digit);
            } else {
                /* 取运算符 */
                while(operators.size() && !priority(s[index],operators.top()))
                    calc(operands,operators);
                operators.push(s[index]);
                index++;    
            }    
        }
        /* 保存最后一次运算 */
        while(operators.size())
            calc(operands,operators);
        return operands.top();
    }

    void calc(stack<int>& operands,stack<int>& operators){
        int result;
        int rhs = operands.top();operands.pop();//右操作数
        int lhs = operands.top();operands.pop();//左操作数
        switch(operators.top()){
            case '+':result = lhs + rhs; break;
            case '-':result = lhs - rhs; break;
            case '*':result = lhs * rhs; break;
            case '/':result = lhs / rhs; break; 
            default: ;
        }
        operators.pop();         //计算完成后，该运算符要弹栈
        operands.push(result);   //将新计算出来的结果入栈
        return;
    }

    /* a 的优先级是否高于 b */
    bool priority(int a,int b){
        if(a == '+' || a == '-')
            return false;
        else if(a=='*' || a=='/')
            return (b=='+' || b == '-');
        return false;
    }
};

// 作者：Nehzil
// 链接：https://leetcode-cn.com/problems/basic-calculator-ii/solution/by-nehzil-drcn/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。